package com.code.test.second.array;

import java.util.Arrays;

public class SCode209 {
    public static void main(String[] args) {
        int[] arr = {2, 3, 1, 2, 4, 3};
        int len = minSubArrayWithLog(arr, 7);
        System.out.println(len);

    }

    /**
     * 209. 最大子数组长度
     * 力扣题目链接
     *
     * 给定一个含有n个正整数的数据库和一个正整数s，确定该数据库满足其和≥s的长度最小的连续子数据库，并返回其长度。如果不存在符合条件的子数据库，返回0 。
     */

    /**
     * 找出子数组，子数组的和小于目标值，
     * 该子数组的元素需要是连续的
     */
    /**
     * 时间复杂度:O(n^2)
     * 空间复杂度:O(1)
     */
    public static int subArray(int[] nums, int s) {
        int ret = Integer.MAX_VALUE;
        int subLen = 0;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            //每次都重置
            sum = 0;
            for (int j = i; j < nums.length; j++) {
                //累加，看是否符合和>=s
                sum += nums[j];
                if (sum >= s) {
                    subLen = j - i + 1;
                    //这里需要一直更新ret，因为要找的是最短子序列
                    ret = ret < subLen ? ret : subLen;
                    //找的是最短子序列
                    break;
                }
            }
        }
        return ret == Integer.MAX_VALUE ? 0 : ret;
    }


    /**
     * 时间复杂度
     * O(n)
     * while循环里，每个元素都是被操作1次，加外面for循环是2次
     */
    public static int subArrayWindow(int[] nums, int val) {
        int sum = 0;
        int subLen = 0;
        int i = 0;
        int ret = Integer.MAX_VALUE;
        for (int j = 0; j < nums.length; j++) {
            sum += nums[j];
            while (sum >= val) {
                //如果已经满足>=val的要求
                subLen = j - i + 1;
                //如果当前这个更小，则使用这个更小的
                ret = ret < subLen ? ret : subLen;
                //不断更新左指针的值，一直往右移动:i++,然后把这个总和减少
                //一直缩短这个窗口，i..j,为一个窗口，然后继续更新知道不符合，然后再换下一个窗口
                //其实只会减1次，因为减完就不满足了，目标是移动窗口的左指针而已
                sum -= nums[i++];
                //然后每个敞口都更新ret的大小
            }
        }
        return ret == Integer.MAX_VALUE ? 0 : ret;
    }

    /**
     * 只是上面解法的while实现
     */
    public static int minSubArrayLen(int[] arr, int target) {
        int sum = arr[0];
        int result = Integer.MAX_VALUE;
        int i = 0, j = 0;

        while (true) {
            if (sum < target) {
                if (j >= arr.length - 1) {
                    break;
                }
                //如果窗口总和<target
                sum += arr[++j];
            } else {
                //如果窗口总和>=target
                result = Math.min(result, j - i + 1);
                sum -= arr[i];
                i++;
            }
        }

        return result;
    }

    public static int minSubArrayWithLog(int[] nums, int target) {
        System.out.println("原始数组：" + Arrays.toString(nums));
        //采用滑动窗口
        int left = 0;
        int right = 0;
        int sum = 0;
        int ret = Integer.MAX_VALUE;
        for (right = 0; right < nums.length; right++) {
            //先滑动右区间right
            sum += nums[right];
            while (sum >= target) {
                //为什么要+1，[1,2,3,4,5] 子区间[2,3,4]下标是1和3，,3-1+1是因为统计的是数量而不是差值，需要加上开始
                //用闭区间开看+1
                int subLen = right - left + 1;
                ret = ret < subLen ? ret : subLen;

                System.out.println("当前窗口:" + Arrays.toString(Arrays.copyOfRange(nums, left, right+1)));

                //滑动窗口左侧
                sum -= nums[left];
                left++;
            }
        }
        return ret == Integer.MAX_VALUE ? 0 : ret;
    }
}
